package com.study.algo;

public class SortAlgo
{
    public static void bubbleSort(int[] arr)
    {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, i, j);
                }
            }
        }
    }

    public static void selectSort(int[] arr)
    {
        // 外层遍历未排序区间的左边界
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[i]) {
                    swap(arr, i, j);
                }
            }
        }
    }

    public static void insertSort(int[] arr)
    {
        // 1、找出无序区间的开始索引
        int startIndex = 1;
        while (startIndex < arr.length && arr[startIndex] >= arr[startIndex - 1]) {
            // 大于等于前一个元素，就至少从下一个索引开始的
            startIndex++;
        }
        // 2、取出无序区间的每一个元素插入到左侧有序区间中
        for (int i = startIndex; i < arr.length; i++) {
            int insertValue = arr[i];
            // 插入位置
            int insertIndex = i;
            while (insertIndex > 0 && arr[insertIndex - 1] > insertValue) {
                arr[insertIndex] = arr[insertIndex - 1];
                // 插入位置前面的元素大于待插入值，插入位置还要前移
                insertIndex--;
            }
            if (insertIndex < i) {
                arr[insertIndex] = insertValue;
            }
        }
    }

    private static void swap(int[] arr, int index1, int index2)
    {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }
}
